#include "graph.hh"
#include "utilis.hh"

#include <iostream>
#include <fstream>
#include <string>

using namespace std;

Path::Path() {
	path = new list<int>;
}

Path::Path(Path * p) {
	path = new list<int>;
	for (list<int>::iterator it = p->path->begin(); it != p->path->end(); it++) {
		path->push_back(*it);
	}
}

bool Path::IsEmpty()
{
	return path->empty();
}

bool FindIJ(Path* p, int i, int j, list<int>::iterator & itA, list<int>::iterator & itB)
{
	list<int>::iterator it1A = p->path->begin();
	list<int>::iterator it1B = p->path->end();

	while(it1A!=it1B && *it1A!=i && *it1A!=j)
		it1A++;

	if(it1A==it1B)
		return false;
	else
		itA = it1A;

	int _e = (*itA==i ? j : i);

	while(it1A!=it1B && *it1A!=_e)
		it1A++;

	if(it1A==it1B)
		return false;
	else
		itB = it1A;

	return true;
}

void Path::Replace(Path * p, int u, int v)
{
	list<int>::iterator it1A, it1B;
	list<int>::iterator it2A, it2B;

	//cout << "u, v: " << u+1 << " " << v+1 << endl;
	//PrintPath(this);
	//PrintPath(p);
	int findA = FindIJ(this, u, v, it1A, it1B);
	int findB = FindIJ(p, u, v, it2A, it2B);
	//cout << "findA, findB: " << findA << " " << findB << endl;

	if(!findA || !findB) {
		cout << "[ERROR][Path::Replace]: Not found i or j" <<"\n";
	}
	else {
		//cout << "it1A, it1B: " << *it1A +1 << " " << *it1B +1 <<"\n";
		//cout << "it2A, it2B: " << *it2A +1 << " " << *it2B +1 <<"\n";

		if(*it2A == *it1A)
		{
			it1A = it1B = path->erase(it1A, it1B);
			while(it2A != it2B)
			{
				it1A = path->insert(it1A, *it2A);
				it1A++;
				it2A++;
			}
		}
		else
		{
			it1A = it1B = path->erase(it1A, it1B);
			while(it2A != it2B)
			{
				it1A = path->insert(it1A, *it2B);
				it1A++;
				it2B--;
			}
		}
	}

	//PrintPath(this); cout << endl;
	//cout << endl;

}

Path* Path::SubPath(int i, int j) {

	list<int>::iterator itA;
	list<int>::iterator itB;
	Path * sub_path = new Path();

	if(!FindIJ(this, i, j, itA, itB)) {
		cout << "[ERROR][Path::SubPath]: Not found i or j" <<"\n";
		return NULL;
	}

	itB++;

	for (list<int>::iterator it=itA; it!=itB ; ++it)
		sub_path->path->push_front(*it);

	return sub_path;
}

bool Path::Contains(Path* p)
{
	int i = p->path->front();
	int j = p->path->back();

	list<int>::iterator it1A, it1B;
	list<int>::iterator it2A, it2B;

	if(!FindIJ(this, i, j, it1A, it1B)) {
		//cout << "Not found i or j" << endl;
		return false;
	}

	if(!FindIJ(p, i, j, it2A, it2B)) {
		cout << "[ERROR][Path::Contains]: Not found i or j" <<"\n";
		return false;
	}

	if(*it2A == *it1A)
	{
		while(it1A!=it1B && it2A!=it2B)
		{
			if(*it1A!=*it2A) return false;

			it1A++;
			it2A++;
		}

		if(*it1A==*it2A) return true;
	}
	else
	{
		while(it1A!=it1B && it2A!=it2B)
		{
			if(*it1A!=*it2B) return false;

			it1A++;
			it2B--;
		}

		if(*it1A==*it2B) return true;
	}

	return false;
}

bool Path::Contains(int node) {

	for (list<int>::iterator it=path->begin(); it != path->end(); ++it)
		if ((*it)==node) return true;

	return false;
}

 bool Path::Contains(pair<int,int> * edge) {
	list<int>::iterator _it;
    for (list<int>::iterator it=path->begin(); it != path->end(); ++it) {
        if (*it == edge->first || *it == edge->second) {
        	if (*it == edge->first) {
            	_it = it;
            	_it++;
            	 return (*_it == edge->second);
        	}
        	else {
            	_it = it;
            	_it++;
            	 return (*_it == edge->first);
        	}
        }
    }
    return false;
 }


 int Path::Length() {
	return path->size();
 }

int& Path::operator[](int x)
{
	list<int>::iterator it = path->begin();
	advance(it, x);

	return (*it);
}


int Path::Size(){
	return path->size();
}

Path::~Path() {

	path->clear();
	delete path;
}

// Constructors

PathMatrix::PathMatrix() {
	sizeP = 0;
	P = NULL;
}


PathMatrix::PathMatrix(int size)
{
	sizeP = size;

	P = new list<Path*> **[size];

	for(int i=0; i<size; i++)
	{
		P[i] = new list<Path*> *[size];
		for(int j=i; j<size; j++)
		{
			P[i][j] = new list<Path*>;
		}
	}

}

PathMatrix::PathMatrix(PathMatrix * _PM)
{
	sizeP = _PM->sizeP;

	P = new list<Path*> **[sizeP];

	for(int i=0; i<sizeP; i++)
	{
		P[i] = new list<Path*> *[sizeP];
		for(int j=i; j<sizeP; j++)
		{
			P[i][j] = new list<Path*>();
			for (list<Path*>::iterator it=_PM->P[i][j]->begin(); it != _PM->P[i][j]->end(); ++it)
				P[i][j]->push_front(new Path(*it));
		}
	}

}


bool PathMatrix::IsNodeDisjointTo(Path* p, int i, int j)
{
	Path * path_aux;
	int aux;

	if (i>j) {
		aux = i;
		i=j;
		j = aux;
	}

	for (list<Path * >::iterator it0=P[i][j]->begin(); it0 != P[i][j]->end(); ++it0) {
		path_aux = *it0;

		if(path_aux->Length() == 2) {
			if((path_aux->path->front() == i &&  path_aux->path->back() == j) || (path_aux->path->front() == j &&  path_aux->path->back() == i)) {
				// el camino es la ariasta (i, j) o (j, i)
				return false;
			}
		}
		else {
			for (list<int>::iterator it1=p->path->begin(); it1 != p->path->end(); ++it1)
				if (*it1!=i && *it1!=j && path_aux->Contains(*it1)) return false;
		}
	}

	return true;
}

void PathMatrix::Add(Path* p, int i, int j)
{
	if (i<=j)
		P[i][j]->push_front(p);
	else
		P[j][i]->push_front(p);
}


void PathMatrix::Update(Path* p_old, Path* p_new) {

	for(int i=0; i<sizeP; i++) {
		for(int j=i; j<sizeP; j++) {
			for (list<Path*>::iterator it=P[i][j]->begin(); it != P[i][j]->end(); ++it)
				if((*it)->Contains(p_old)) (*it)->Replace(p_new, p_old->path->front(), p_old->path->back());
		}
	}
}


bool PathMatrix::Contains(Path * p, int i, int j) {

	for (list<Path*>::iterator it=P[i][j]->begin(); it != P[i][j]->end(); ++it)
			if((*it)->Contains(p)) return true;

	return false;
}

list<Path*> **& PathMatrix::operator[](int x)
{
	return P[x];
}

PathMatrix::~PathMatrix()
{
	if (P) {
		for(int i=0; i<sizeP; i++)
		{
			for(int j=i; j<sizeP; j++)
			{
				for (list<Path*>::iterator it=P[i][j]->begin(); it != P[i][j]->end(); ++it)
					delete *it;

				P[i][j]->clear();
				delete P[i][j];
			}
			delete[] P[i];
		}
		delete[] P;
	}

	sizeP = 0;
}

Graph::Graph()
{
	sizeG = 0;
	diameter = 0;
	T = NULL;
	_T = NULL;
	W = NULL;
	actived_node = NULL;

	R = NULL;
	C = NULL;
	E = NULL;
}


Graph::Graph(int G_size)
{
	sizeG = G_size;
	diameter = 0;
	T = new list<int>;
	_T = new int[sizeG];
	W = new int[sizeG];
	actived_node = new int[sizeG];

	R = new int*[sizeG];
	C = new int*[sizeG];
	E = new int*[sizeG];
	for(int i=0; i<sizeG; i++)
	{
		C[i] = new int[sizeG];
		E[i] = new int[sizeG];
		R[i] = new int[sizeG];
	}


	for(int i=0; i<sizeG; i++)
	{
		_T[i] = 0;
		W[i] = 0;
		actived_node[i] = 0;

		for(int j=0; j<sizeG; j++)
		{
			C[i][j] = 0;
			E[i][j] = 0;
			R[i][j] = 0;
		}
	}
}


Graph::Graph(Graph* G)
{
	sizeG = G->sizeG;
	diameter = G->diameter;
	T = new list<int>;

	for (list<int>::iterator it=G->T->begin(); it != G->T->end(); ++it)
		T->push_front(*it);

	_T = new int[sizeG];
	W = new int[sizeG];
	actived_node = new int[sizeG];

	R = new int*[sizeG];
	C = new int*[sizeG];
	E = new int*[sizeG];
	for(int i=0; i<sizeG; i++)
	{
		C[i] = new int[sizeG];
		E[i] = new int[sizeG];
		R[i] = new int[sizeG];
	}


	for(int i=0; i<sizeG; i++)
	{
		_T[i] = G->_T[i];
		W[i] = G->W[i];
		actived_node[i] = G->actived_node[i];

		for(int j=0; j<sizeG; j++)
		{
			C[i][j] = G->C[i][j];
			E[i][j] = G->E[i][j];
			R[i][j] = G->R[i][j];
		}
	}

}

void Graph::Add(Path* p) {
	list<int>::iterator _it , end;

	end = p->path->end(); end--;
	for (list<int>::iterator it=p->path->begin(); it != end; ++it) {
		_it = it;
		_it++;
		actived_node[*it] = 1;
		SetMatrix(E, *it, *_it, 1);
	}
	actived_node[p->path->back()] = 1;
}

void Graph::Substract(Path* p) {

	list<int>::iterator _it , end;

	end = p->path->end(); end--;
	for (list<int>::iterator it=p->path->begin(); it != end; ++it) {
		_it = it;
		_it++;
		actived_node[*it] = 0;
		SetMatrix(E, *it, *_it, 0);
	}
	actived_node[p->path->back()] = 0;
}

void Graph::SubstractWithoutExtremes(Path * p) {

	list<int>::iterator _it , end;
	int _e;
	int u = p->path->front();
	int v = p->path->back();

	end = p->path->end(); end--;
	for (list<int>::iterator it=p->path->begin(); it != end; ++it) {
		_it = it;
		_it++;
		if(*it!=u && *it!=v)  actived_node[*it] = 0;
		SetMatrix(E, *it, *_it, 0);
	}

	_e = p->path->back();
	if(_e!=u && _e!=v)  actived_node[_e] = 0;
}

void Graph::Substract(list<Path*> * paths) {
	for (list<Path*>::iterator it=paths->begin(); it != paths->end(); ++it)
		Substract(*it);
}

void Graph::SubstractWithoutExtremes(list<Path*> * paths) {
	for (list<Path*>::iterator it=paths->begin(); it != paths->end(); ++it)
		SubstractWithoutExtremes(*it);
}

int Graph::GetNodeGrade(int node)
{
	int grade = 0;

	if (actived_node[node]) {
		for(int i=0; i<sizeG; i++)
			if(actived_node[i] && GetMatrix(E, node, i))
				grade++;
	}

	return grade;
}

bool Graph::IsTerminal(int node)
{
	return (actived_node[node] && _T[node]);
};

list<int> * Graph::GetNeighbors(int node)
{
	list<int> * neighbors = new list<int>;

	if (actived_node[node])
	{
		for(int i=0; i<sizeG; i++)
			if( actived_node[i] && GetMatrix(E, node, i)) neighbors->push_front(i);
	}

	return neighbors;
}

list<int> * Graph::GetNeighbors(int node, list<int> * candidates) {

	list<int> * neighbors = new list<int>;

	if (actived_node[node])
	{
		for (list<int>::iterator it= candidates->begin(); it != candidates->end(); ++it)
			if(actived_node[*it] && GetMatrix(E, node, *it)) neighbors->push_front(*it);
	}

	return neighbors;
}


int Graph::Cost()
{
	//cout << "////////////////////////////////////////////////////////////////DELETE BEFORE Cost()" << endl;
	int cost = 0;

	for(int i=0; i<sizeG; i++) {
		if (actived_node[i]) {
			cost+=W[i];
			for(int j=i; j<sizeG; j++)
				if (actived_node[j] && E[i][j]) cost+=C[i][j];
		}
	}

	//cout << "///////////////////////////////////////////////////////////////DELETE AFTER Cost()" << endl;
	return cost;
}

int Graph::CostPath(Path * p) {

	int cost = 0;

	list<int>::iterator _it , end;
	end = p->path->end();
	end--;
	for (list<int>::iterator it=p->path->begin(); it != end; ++it)
	{
		_it = it;
		_it++;
		//cout << W[*it] << "   " << GetMatrix(C, *it, *_it) << "   " << *it+1 << "   " << *_it+1 <<endl;
		cost += W[*it] + GetMatrix(C, *it, *_it);
	}

	//cout << W[p->path->back()] << "   " << p->path->back()+1 <<endl;
	cost += W[p->path->back()]; // sumo el ultimo nodo que quedo sin sumar

	return cost;
}

Graph::Graph(const char* path)
{
	sizeG = 0;
	diameter = 0;
	T = NULL;
	_T = NULL;
	W = NULL;
	actived_node = NULL;

	R = NULL;
	C = NULL;
	E = NULL;

	FileToGraph(path, this);
}



void Graph::Dump(char * file_path)
{
	ofstream file(file_path);

	if(file.is_open())
	{
		if((sizeG > 0) && actived_node && E && _T) {

			file << "SECTION Nodes" << endl;
			for(int i=0; i<sizeG; i++)
				if(actived_node[i]) {
					if(_T[i])
						file << "T " << i+1 << " " << W[i] << endl;
					else
						file << "O " << i+1 << " " << W[i] << endl;
				}

			file << "END" << endl;

			file << endl;

			file << "SECTION Edges" << endl;
			for(int i=0; i<sizeG; i++)
				if (actived_node[i]) {
					for(int j=i; j<sizeG; j++)
						if(actived_node[j] && E[i][j])
							file <<"E " << i+1 << " " << j+1 << " "  << C[i][j] << endl;
				}
			file << "END" << endl;

			file << endl;

			file << "SECTION Cost" << endl;
			file << "C " << Cost() << endl;
			file << "END" << endl;

		}
		else {
			file << "[ERROR][Graph::Dump]: Graph infeasible, some attributes are null." << endl;
		}


		file.close();
	}
	else cout << "[ERROR][Graph::Dump]: Unable to open file" << endl;
}


Graph::~Graph()
{
	if(T) {
		T->clear();
		delete T;
	}

	if(_T) delete[] _T;

	if(W) delete[] W;
	if(actived_node) delete[] actived_node;

	if(C && R && E) {
		for(int i=0; i<sizeG; i++)
		{
			if(C[i]) delete[] C[i];
			if(R[i]) delete[] R[i];
			if(E[i]) delete[] E[i];
		}

		delete[] R;
		delete[] C;
		delete[] E;
	}

	sizeG = 0;
	diameter = 0;
}
